#include <iostream>
#include <algorithm>
#include <stdlib.h>

int* merge(int res[], int L[], int mid1, int R[], int mid2)
{
    int i=0, j=0;

    while (i < mid1 || j < mid2)
    {
        if (i < mid1 && j < mid2)
        {
            if (L[i] <= R[j])
            {
              res[i+j] = L[i];
              i++;
            }
            else
            {
                res[i+j] = R[j];
                j++;
            }
        }
        else
            if (i<mid1)
            {
                res[i+j]=L[i];
                i++;
            }
            else
                if (j<mid2)
                {
                    res[i+j]=R[j];
                    j++;
                }
    }
    return res;
}

int* mergeSort(int mas[], int dl)
{
    int i, *otv;
    if (dl > 1)
    {
        int mid1 = dl / 2;
        int mid2 = dl - mid1;
        int* L = new int[mid1];
        int* R = new int[mid2];

        for (i = 0; i<dl; i++)
        {
            if (i<mid1)
                L[i] = mas[i];
            else
                R[i-mid1] = mas[i];
        }

        mergeSort(L, mid1);
        mergeSort(R, mid2);
        otv=merge(mas, L, mid1, R, mid2);

        delete[] L;
        delete[] R;
    }

    return otv;

}

int main()
{
    int *res;
    /*int mas[9] = { 2,10,3,77,5,1,9,8,1 };


    for (int i=0; i<9; i++)
        printf("%i ", mas[i]);
    printf("\n");
    */

    int *mas1 = new int[1000000];
    for (int i=0; i<1000000; i++)
    {
        mas1[i]=rand();
        //printf("%i ", mas[i]);
    }
    printf("\n");

    int *mas2 = new int[1000000];
    for (int i=0; i<1000000; i++)
    {
        mas2[i]=mas1[i];
        //printf("%i ", mas[i]);
    }
    printf("\n");

    std::sort(mas2, mas2+1000000);
    res=mergeSort(mas1, 1000000);

    for (int i=0; i<1000000; i++)
    {//    printf("%i ", res[i]);
        if (res[i]!=mas2[i])
                printf("ERROR");
    }
    delete[] mas1;
    delete[] mas2;
    return 0;
}

